package com.scqzy.shengchunqiang.sword2offer.day16;

/**
 * @Description: 剑指 Offer 61. 扑克牌中的顺子
 * @Author 盛春强
 * @Date 2021/8/23 15:52
 */
public class IsStraight {
    public static void main(String[] args) {
        int[] ranArr = new int[]{0, 0, 8, 5, 4};
        IsStraight straight = new IsStraight();

        System.out.println(straight.isStraight(ranArr));

    }

    public boolean isStraight(int[] nums) {
        // 写个归并
        mergeSort(nums, 0, nums.length - 1);
        int zNum = 0;
        int mSum = 0;
        for (int i = nums.length - 1; i >= 1; i--) {
            if (nums[i - 1] == 0) {
                zNum = i;
                break;
            }
            if (nums[i] == nums[i - 1]) {
                return false;
            }
            mSum += (nums[i] - nums[i - 1] - 1);
        }
        return zNum >= mSum;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int p = 0;
        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            tmp[p++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) {
            tmp[p++] = nums[i++];
        }
        while (j <= right) {
            tmp[p++] = nums[j++];
        }
        System.arraycopy(tmp, 0, nums, left, right - left + 1);
    }
}
